// 文件名：set_dictionary_index.cpp
// 目的：演示在有序字典（std::set）中进行：精确查找、前缀枚举、以及定位某词的“就近位置”（前驱/后继）。
// 要点：
//   - std::set<std::string, std::less<>> 使用透明比较器 std::less<>，支持异构查找（如 string_view）；
//   - find(key)：O(log N) 精确匹配；
//   - lower_bound(key)：返回第一个不小于 key 的迭代器，用于前缀枚举的起点及“接近项”定位；
//   - 前缀枚举：从 lower_bound(prefix) 起向后遍历，逐个检查是否仍以 prefix 开头；
//   - “就近位置”：lower_bound("bax") 给出不小于 "bax" 的后继；其前一个（若存在）为前驱。
// 复杂度：查找/边界：O(log N)，枚举 K 个匹配项总计 O(log N + K)。
// 注意：
//   - 下面前缀枚举示例中将 string_view 转为 std::string 传入 lower_bound；也可直接用 string_view（因 std::less<> 透明）。
//   - 字典序基于字符编码（ASCII/UTF-8 单字节字符时等价），多字节编码的词典序需谨慎处理。

#include <iostream>
#include <set>
#include <string>
#include <string_view>

int main() {
    // 初始化词汇表（按字典序自动排序）
    std::set<std::string, std::less<>> glossary = {
        "apple", "application", "apply", "banana", "band", "bandwidth",
        "cherry", "date", "delta", "zebra"
    };

    // 1) 精确查找
    auto containsTerm = glossary.find("banana") != glossary.end();
    std::cout << "Contains 'banana'? " << std::boolalpha << containsTerm << '\n';

    // 2) 前缀枚举：列出所有以 "app" 开头的单词
    std::string_view prefix = "app";
    // 可写作：auto it = glossary.lower_bound(prefix); // 若启用透明比较器，直接用 string_view 即可
    auto it = glossary.lower_bound(std::string(prefix));
    std::cout << "Words with prefix \"" << prefix << "\":";
    for (; it != glossary.end(); ++it) {
        if (it->compare(0, prefix.size(), prefix) != 0) break; // 一旦不匹配即停止
        std::cout << ' ' << *it;
    }
    std::cout << '\n';

    // 3) 就近定位：lower_bound("bax") 给出后继，前驱为其前一个（若存在）
    std::cout << "Lexicographically closest to 'bax': ";
    auto lower = glossary.lower_bound("bax");
    if (lower != glossary.begin()) {
        auto prev = std::prev(lower);
        std::cout << "'" << *prev << "' before, ";
    } else {
        std::cout << "(none before), ";
    }
    if (lower != glossary.end()) {
        std::cout << "'" << *lower << "' after.\n";
    } else {
        std::cout << "(none after).\n";
    }

    return 0;
}